class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        DP = [-1 for _ in range(m * n)]
        out = [0] * len(positions)
        self.island = 0

        def find(x):
            if DP[x] == x:
                return x
            else:
                DP[x] = find(DP[x])
                return DP[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    DP[rooty] = rootx
                else:
                    DP[rootx] = rooty
                self.island -= 1

        for i, item in enumerate(positions):
            index = item[0] * n + item[1]
            if DP[index] == -1:
                DP[index] = index
                self.island += 1
            for ux, uy in [(item[0] - 1, item[1]), (item[0] + 1, item[1]), (item[0], item[1] - 1),
                           (item[0], item[1] + 1)]:
                if 0 <= ux < m and 0 <= uy < n:
                    if DP[ux * n + uy] >= 0:
                        union(index, ux * n + uy)
            out[i] = self.island
        return out


data = Solution()
# m = 3
# n = 3
# positions = [[0, 0], [0, 1], [1, 2], [2, 1]]
# print(data.numIslands2(m, n, positions))
# m = 2
# n = 2
# positions = [[0, 0], [1, 1], [0, 1]]
# print(data.numIslands2(m, n, positions))
# m = 8
# n = 2
# positions = [[7, 0]]
# print(data.numIslands2(m, n, positions))
m = 3
n = 3
positions = [[0, 0], [0, 1], [1, 2], [1, 2]]
print(data.numIslands2(m, n, positions))
m = 8
n = 4
positions = [[0, 0], [7, 1], [6, 1], [3, 3], [4, 1]]
print(data.numIslands2(m, n, positions))
